package leetcode_day._2023._12;

/**
 * 2132.用邮票贴满网格图
 * 算法: 前缀和 + 差分数组
 * <p>
 * 使用前缀和统计矩形是否可以贴上邮票
 * 使用差分数组统计每个空位置的格子可以贴的邮票数量
 *
 * @author yezh
 * @date 2023/12/14 15:55
 */
public class _14 {

    // 13:55 ~ 15:05
    public boolean possibleToStample_time_limit_exceeded(int[][] grid, int stampHeight, int stampWidth) {
        int m = grid.length, n = grid[0].length;
        // dp[i][j]: [0, 0] 到 [i - 1, j - 1] 所形成的矩形的 1 的数量
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + grid[i - 1][j - 1];
        // [a, b] 到 [c, d] 形成的矩形的 1 的数量
        // dp[c][d] - dp[c][d - W - 1] - dp[a - 1][d - H - 1] + dp[a - 1][b - 1]
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    // 高度: [Math.max(0, i - stampHeight + 1), Math.min(m - 1, i + stampHeight - 1)]
                    // 宽度: [Math.max(0, j - stampWidth + 1), Math.min(n - 1, j + stampWidth - 1)]
                    int hMin = Math.max(0, i - stampHeight + 1), hMax = Math.min(m - 1, i + stampHeight - 1);
                    if (hMax - hMin + 1 < stampHeight) return false;
                    int wMin = Math.max(0, j - stampWidth + 1), wMax = Math.min(n - 1, j + stampWidth - 1);
                    if (wMax - wMin + 1 < stampWidth) return false;
                    boolean flag = true;
                    // 这里超时
                    for (int a = hMin + stampHeight - 1; a <= hMax; a++)
                        for (int b = wMin + stampWidth - 1; b <= wMax; b++) {
                            int x = a - stampHeight + 1, y = b - stampWidth + 1;
                            int cnt1 = dp[a + 1][b + 1] - dp[a + 1][y] - dp[x][b + 1] + dp[x][y];
                            if (cnt1 == 0) {
                                flag = false;
                                break;
                            }
                        }
                    if (flag) return false;
                }
            }
        return true;
    }

    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int m = grid.length, n = grid[0].length;

        // 前缀和
        int[][] prefix = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                prefix[i][j] = prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1] + grid[i - 1][j - 1];

        // 差分数组
        int[][] difference = new int[m + 2][n + 2];
        for (int i2 = stampHeight; i2 <= m; i2++)
            for (int j2 = stampWidth; j2 <= n; j2++) {
                // [i - stampHeight, j - stampWidth] ~ [i, j] 组成的矩阵中每个元素值增加了 1
                int i1 = i2 - stampHeight + 1, j1 = j2 - stampWidth + 1;
                if (prefix[i2][j2] - prefix[i2][j1 - 1] - prefix[i1 - 1][j2] + prefix[i1 - 1][j1 - 1] == 0) {
                    difference[i1][j1]++;
                    difference[i2 + 1][j1]--;
                    difference[i1][j2 + 1]--;
                    difference[i2 + 1][j2 + 1]++;

                }
            }

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                difference[i][j] += difference[i][j - 1] + difference[i - 1][j] - difference[i - 1][j - 1];
                if (grid[i - 1][j - 1] == 0 && difference[i][j] == 0)
                    return false;
            }
        return true;
    }

}
